package graph

import "github.com/tidwall/btree"

// NewDigraph 返回一个有向图
func NewDigraph() *Digraph {
	digraph := &Digraph{
		Vertexes: btree.NewBTreeG[*Item](ItemLess),
		Edges:    btree.NewBTreeG[*Item](ItemLess),
	}
	// 默认添加两个特殊的顶点
	// 可能存在所有顶点的入顶点；
	// 可能存在所有顶点的出顶点。
	digraph.AddVertex(NewVertex(GetAllInConnectionPoints()))
	digraph.AddVertex(NewVertex(GetAllOutConnectionPoints()))
	return digraph
}

// AddVertex 添加顶点
func (g *Digraph) AddVertex(vertex *Vertex) {
	g.Vertexes.Set(NewItem(vertex.GetName(), vertex, nil))
}

// AddVertexes 批量添加顶点
func (g *Digraph) AddVertexes(vertexes ...*Vertex) {
	for _, v := range vertexes {
		g.AddVertex(v)
	}
}

// AddVertexWithEdge 添加顶点，及其相关的入边和出边
//
// 在有向图中，一个顶点并不知道自己是哪些顶点的邻接顶点，因此添加顶点时需要指定入边。
// 但它自己有邻接顶点，因此可以对应添加出边。
func (g *Digraph) AddVertexWithInEdges(vertex *Vertex, inEdges ...*Edge) {
	// 添加顶点本身
	g.AddVertex(vertex)

	// 通过入边找到对应的顶点，并在这些顶点的邻接链表中加入该顶点
	for _, e := range inEdges {
		g.Vertexes.Scan(func(item *Item) bool {
			if item.Vertex.Out.Equal(e.From) {
				item.Vertex.AddAdjacent(vertex)
			}
			return true
		})
	}

	// 添加入边
	for _, e := range inEdges {
		g.AddEdge(e)
	}

	// 添加出边
	vertex.AdjacentVertexes.Scan(func(item *Item) bool {
		g.AddEdge(NewEdge(vertex.Out, item.Vertex.In))
		return true
	})
}

// GetVertex 根据端点返回顶点
func (g *Digraph) GetVertex(in, out *ConnectionPoint) *Vertex {
	item, ok := g.Vertexes.Get(NewItem(NewVertex(in, out).GetName(), nil, nil))
	if ok {
		return item.Vertex
	}
	return nil
}

// GetVertexList 根据入/出端点获取顶点
//
// 获得的是并集，当in和out不属于一个顶点时将返回两个顶点
func (g *Digraph) GetVertexList(in, out *ConnectionPoint) []*Vertex {
	var vertexLs []*Vertex
	vertexs := make(map[string]struct{})
	g.Vertexes.Scan(func(item *Item) bool {
		name := item.Vertex.GetName()
		if _, ok := vertexs[name]; !ok && (item.Vertex.In.Equal(in) || item.Vertex.Out.Equal(out)) {
			vertexs[name] = struct{}{}
			vertexLs = append(vertexLs, item.Vertex)
		}
		return true
	})
	return vertexLs
}

// DeleteVertex 删除顶点
//
// 1、删除顶点本身；
// 2、删除出边：边的 from 是顶点的 out；
// 3、删除入边：边的 to 是顶点的 in；
// 4、删除邻接顶点：顶点 out 是第3点中边的 from，从该顶点的邻接顶点中删除 vertex；
func (g *Digraph) DeleteVertex(vertex *Vertex) {
	inEdgeLs, outEdgeLs := g.GetEdgeList(vertex)

	// 获得所有邻接顶点为 vertex 的顶点，并从这些顶点的邻接顶点中删除 vertex
	var vertexLs []*Vertex
	for _, e := range inEdgeLs {
		vertexLs = append(vertexLs, g.GetVertexList(nil, e.From)...)
	}
	for _, v := range vertexLs {
		v.DeleteAdjacent(vertex)
	}

	// 删除出边
	for _, e := range outEdgeLs {
		g.DeleteEdge(e)
	}

	// 删除入边
	for _, e := range inEdgeLs {
		g.DeleteEdge(e)
	}

	// 删除顶点本身
	g.Vertexes.Delete(NewItem(vertex.GetName(), nil, nil))
}

// AddEdge 添加边
func (g *Digraph) AddEdge(edge *Edge) {
	g.Edges.Set(NewItem(edge.GetName(), nil, edge))
}

// AddEdgeBetweenVertexes 在那两个顶点之间添加边
//
// 同步添加邻接顶点
func (g *Digraph) AddEdgeBetweenVertexes(from, to *Vertex) {
	g.AddEdge(NewEdge(from.Out, to.In))
	from.AddAdjacent(to)
}

// AddEdgeBetweenVertexesWithApi 在那两个顶点之间添加边，并设置 API 信息
//
// 同步添加邻接顶点
func (g *Digraph) AddEdgeBetweenVertexesWithApi(from, to *Vertex, api *Api) {
	edge := NewEdge(from.Out, to.In)
	edge.Api = api
	g.AddEdge(edge)
	from.AddAdjacent(to)
}

// DeleteEdge 删除边
func (g *Digraph) DeleteEdge(edge *Edge) {
	g.Edges.Delete(NewItem(edge.GetName(), nil, edge))
}

// DeleteEdgeBetweenVertexes 删除两个顶点之间的边
func (g *Digraph) DeleteEdgeBetweenVertexes(from, to *Vertex) {
	g.DeleteEdge(NewEdge(from.Out, to.In))
	from.DeleteAdjacent(to)
}

// GetEdge 返回端点对应的边
func (g *Digraph) GetEdge(from, to *ConnectionPoint) *Edge {
	edge, _ := g.Edges.Get(NewItem(NewEdge(from, to).GetName(), nil, nil))
	if edge != nil {
		return edge.Edge
	}
	return nil
}

// GetEdgeBetweenVertexes 返回两个顶点之间的边
func (g *Digraph) GetEdgeBetweenVertexes(from, to *Vertex) *Edge {
	return g.GetEdge(from.Out, to.In)
}

// GetEdges 返回节点相关的入边和出边
//
// 入边：edge.to == vertex.in
// 出边：edge.from == vertex.out
func (g *Digraph) GetEdgeList(vertex *Vertex) ([]*Edge, []*Edge) {
	var (
		inEdgeLs  []*Edge
		outEdgeLs []*Edge
	)
	g.Edges.Scan(func(item *Item) bool {
		if item.Edge.From.Equal(vertex.Out) {
			outEdgeLs = append(outEdgeLs, item.Edge)
		} else if item.Edge.To.Equal(vertex.In) {
			inEdgeLs = append(inEdgeLs, item.Edge)
		}
		return true
	})
	return inEdgeLs, outEdgeLs
}

// Len 返回顶点个数，边的条数
func (g *Digraph) Len() (int, int) {
	return g.Vertexes.Len(), g.Edges.Len()
}
